package com.fs.leetcode.paixu;

import java.util.Arrays;

/**
 * @author ：hyq
 * @date ：Created in 2020/6/9 16:19
 * @description：
 * @modified By：
 */
public class ShellSort {

    /**
     * 分析使用逐步推导的方式使用
     * @param arr
     */
    public static void shellSort(int[] arr){

        //第一轮排序是将10个数分为5组
//        for(int i =5;i<arr.length;i++){
//            //遍历每个组中的各个元素一共5组每组2个元素
//            for(int j = i-5;j>=0; j -= 5){
//               //使用交换法
//                if (arr[j] > arr[j+5]) {
//                    int temp = arr[j];
//                    arr[j] = arr[j+5];
//                    arr[j+5] = temp;
//                }
//            }
//
//        }
//        System.out.println("第一轮排序后"+Arrays.toString(arr));
//
//        for(int i =2;i<arr.length;i++){
//            //遍历每个组中的各个元素一共5组每组2个元素
//            for(int j = i-2;j>=0; j -= 2){
//                //使用交换法
//                if (arr[j] > arr[j+2]) {
//                    int temp = arr[j];
//                    arr[j] = arr[j+2];
//                    arr[j+2] = temp;
//                }
//            }
//
//        }
//        System.out.println("第二轮排序后"+Arrays.toString(arr));
//
//        for(int i =1;i<arr.length;i++){
//            //遍历每个组中的各个元素一共5组每组2个元素
//            for(int j = i-1;j>=0; j -= 1){
//                //使用交换法
//                if (arr[j] > arr[j+1]) {
//                    int temp = arr[j];
//                    arr[j] = arr[j+1];
//                    arr[j+1] = temp;
//                }
//            }
//
//        }
//        System.out.println("第三轮排序后"+Arrays.toString(arr));

        //==分析结束================
        //将每一轮用for循环替代
        int count = 0;
        //增量gap 逐步缩小gap
        for (int gap = arr.length/2;gap>0;gap /= 2){
            //遍历所有的组
            for(int i =gap;i<arr.length;i++){
                //遍历每个组中的各个元素一共5组每组2个元素
                for(int j = i-gap;j>=0; j -= gap){
                    //使用交换法
                    if (arr[j] > arr[j+gap]) {
                        int temp = arr[j];
                        arr[j] = arr[j+gap];
                        arr[j+gap] = temp;
                    }
                }

            }
            System.out.println("第"+(++count)+"轮排序后为"+Arrays.toString(arr));
        }

        //使用移动法修改希尔排序
        int len = arr.length;
        //分组
        for (int gap = len / 2; gap > 0; gap = gap / 2) {
            for (int i = gap; i < len; i++) {
                int j = i;
                int current = arr[i];
                while (j - gap >= 0 && current <arr[j-gap]){
                    arr[j] = arr[j-gap];
                    j = j-gap;
                }
                //找到位置插入
                arr[j] = current;
            }
            System.out.println("第"+(++count)+"轮排序后为"+Arrays.toString(arr));
        }

    }

    public static void main(String[] args) {
        int[] arr = {8,9,1,7,2,3,5,4,6,0};
        shellSort(arr);
    }
}
